#include <iostream>
#include <stdio.h>
#include <algorithm>
using std::cout;
using std::cin;
using std::endl;
typedef long long LL;
const int N = 77;
int l;
int arr[N][N];
LL sum[N][N];
int A[N];
void solveSUM() {
    LL t = 0;
    sum[0][0] = arr[0][0];
    for (int i=1; i<l; ++i) sum[0][i] = sum[0][i-1] + arr[0][i];
    for (int i=1; i<l; ++i) {
        t = 0;
        for (int j=0; j<l; ++j) {
            t += arr[i][j];
            sum[i][j] = sum[i-1][j] + t;
        }
    }
}

void show() {
    for (int i=0; i<20; ++i) {
        for (int j=0; j<20; ++j) {
            printf("%3d ", arr[i][j]);
        }
        printf("\n");
    }
    printf("-----------vs------------\n");
    for (int i=0; i<20; ++i) {
        for (int j=0; j<20; ++j) {
            printf("%3lld ", sum[i][j]);
        }
        printf("\n");
    }
}
LL getSUM(int n, int m) {
    if (n<0 || m<0) return 0;
    LL t = sum[l-1][l-1];
    LL res1 = n/l;
    LL res2 = m/l;
    LL ret = t*res1*res2;
    LL rem1 = n%l;
    LL rem2 = m%l;
    ret += res1*sum[l-1][rem2];
    ret += res2*sum[rem1][l-1];
    ret += sum[rem1][rem2];
    return ret;
}

int main(int argc, char** argv) {
#ifdef hai
    freopen("in.txt", "r", stdin);
#endif
    int T;
    cin>>T;
    while (T--) {
        scanf("%d", &l);
        for (int i=0; i<l; ++i) {
            scanf("%d", A+i);
        }
        int cursor = 0;
        for (int i = 0; i<N; ++i) {
            for (int j = 0; j <= i; ++j) {
                arr[j][i - j] = A[cursor];
                cursor = (cursor + 1) % l;
            }
        }
        l = 2*l;
        solveSUM();
//        show();
        int x0,y0,x1,y1;
        int T;
        scanf("%d", &T);
        while (T--) {
            scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
            LL t1 = getSUM(x1, y1);
            LL t2 = getSUM(x1, y0-1);
            LL t3 = getSUM(x0-1, y1);
            LL t4 = getSUM(x0-1, y0-1);
 //           printf("%lld %lld %lld %lld\n", t1, t2, t3, t4);
            LL res = t1 - t2 - t3 + t4;
            printf("%lld\n", res);
        }
    }
    return 0;
}
